// 6.49 编写算法判别给定二叉树是否为完全二叉树。
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"
bool fun_6_49(tree *root)
{
    tree *queue[100];
    int rear, front;
    rear = front = 0;
    if (root)
        queue[rear++] = root;
    else
        return false;
    int flag = 0;
    while (front < rear)
    {
        tree *r = queue[front++];
        // case 1
        if (r->left && r->right)
        {
            queue[rear++] = r->left;
            queue[rear++] = r->right;
        }
        // case 2
        if (r->right && !r->left)
            return false;
        // case 3
        if ((r->left && !r->right) || (!r->left && !r->right))
        {
            while (front < rear)
            {
                r = queue[front++];
                if (r->left || r->right)
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    /*******************code*******************/
    int n = 15;
    int a1[15] = {1,
                  2, 3,
                  4, 5, 6, 7,
                  NULL, 9, 10, NULL, NULL, NULL, NULL, NULL};
    tree *root;
    CreatTree(root, a1, n, 0);
    if (fun_6_49(root))
        printf("YES!");
    else
        printf("NO");

    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
